ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group93b.txt/000065_icon-group-sender _Fri May 7 08:15:04 1993.msg

Internet Message Format | 1993-06-16 | 2KB

Received: by cheltenham.cs.arizona.edu; Fri, 7 May 1993 11:40:44 MST
Message-Id: <[e-mail]>
From: Ken Walker <[e-mail]>
Subject: Re: Is this passable code?
To: [e-mail]
Date: Fri, 7 May 93 8:15:04 PDT
In-Reply-To: <[e-mail]>; from "[e-mail]" at Apr 30, 93 7:02 pm
Mailer: Elm [revision: 66.25]
Status: R
Errors-To: [e-mail]

> Don J. Bailey writes:
>
> In article <[e-mail]>, [e-mail] (Nevin ":-]" Liber) writes:
> >
> > procedure Permute(sString)
>    ...
>
> Ok, I understand it's a generator. I understand it's recursive.
> I understand it works because I have run it and traced it. I don't
> understand why it works or how you thought of the design.

Here is a permutation procedure that produces a set of permutations. It
is not as neat as Nevin's recursive generator, but is perhaps a little
easier to follow. Once you understand it, it may be easier to
understand Nevin's code; just think of a generator as returning
elements of a set, one at a time.

# permutations - return the set of all permuation of the characters in s
procedure permutations(s)
   local p, pi, i

   if *s <= 1 then
      return set([s])

   # Choose each character in turn and concatenate it on the front of each
   # of the permutations of the remaining characters.
   p := set()
   every i := 1 to *s do {
     pi := permutations(s[1:i] || s[i+1:0])
     every insert(p, s[i] || !pi)
     }
   return p
end


Ken Walker   [e-mail]